package leetcode_1101_1200;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;

public class LeeCode_1147 {
    public static void main(String[] args) {
        System.out.println(longestDecomposition("abcab"));
        System.out.println(longestDecomposition("ghiabcdefhelloadamhelloabcdefghi"));
        System.out.println(longestDecomposition("merchant"));
        System.out.println(longestDecomposition("antaprezatepzapreanta"));
        System.out.println(longestDecomposition("abcabc"));
        System.out.println(longestDecomposition("bqrcnnqrcb"));
        System.out.println(longestDecomposition("ab"));
    }
    private static int longestDecomposition2(String text) {
        if (text.isEmpty())
            return 0;
        for (int i = 1, n = text.length(); i <= n / 2; ++i) {
            if (text.substring(0, i).equals(text.substring(n - i))){
                return 2 + longestDecomposition2(text.substring(i, n - i));
            }
        }
        return 1;
    }
    private static int longestDecomposition(String text) {
        Map<Character, LinkedList<Integer>> map = new HashMap<>();
        int n = text.length();
        for (int i = 0; i <= (n - 1) / 2; i++) {
            char c = text.charAt(i);
            if (map.containsKey(c)){
                map.get(c).add(i);
            }else {
                LinkedList<Integer> list = new LinkedList<>();
                list.add(i);
                map.put(c, list);
            }
        }
        int ans = 0;
        int i = n - 1;
        while (i > (n - 1) / 2){
            char last = text.charAt(i);
            LinkedList<Integer> is = map.get(last);
            if (is == null){
                return ans + 1;
            }
            for (int j = 0; j < is.size(); j++) {
                int len = is.get(j) - n + 2 + i;
                if (len > 0 && text.substring(n - 1 - i, is.get(j) + 1).equals(text.substring(i - len + 1, i + 1))){
                    ans += 2;
                    if (is.get(j) + 1 == i - len + 1)
                        return ans;
                    is.remove(j);
                    i = i - len;
                    break;
                }
                if (j == is.size() - 1){
                    return ans + 1;
                }
            }
        }
        return ans + 1;
    }
}
